package com.ming.learn.from.carl.binary.tree;

import com.ming.commons.utils.TreeNode;

/*
110.平衡二叉树
 */
public class Of20210310LeetCode110 {
    /*
    给定一个二叉树，判断它是否是高度平衡的二叉树。
    本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
     */
    public static void main(String[] args) {
        System.out.println(isBalanced(new TreeNode(1,new TreeNode(2,new TreeNode(3),null),new TreeNode(4))));
    }

    /*
    递归
     */
    private static int getDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = getDepth(root.left);
        if (leftDepth == -1) return -1;
        int rightDepth = getDepth(root.right);
        if (rightDepth == -1) return -1;
        return Math.abs(leftDepth - rightDepth) > 1 ? -1 : Math.max(leftDepth, rightDepth) + 1;
    }
    private static boolean isBalanced(TreeNode root){
        return getDepth(root)==-1? false:true;
    }

    /*
    迭代法麻烦而且 效率不高
    地址：https://mp.weixin.qq.com/s?__biz=MzUxNjY5NTYxNA==&mid=2247484841&idx=1&sn=fd1380e74ed46c7267b069f3578e2d3a&scene=21#wechat_redirect
     */
}
